package 求100以内素数的个数;

/**
 * 求100以内素数的个数
 */
public class Solution {
    public static void main(String[] args) {
        int count = bf(100);
        System.out.println("count = " + count);
        count = eratosthenes(100);
        System.out.println("count = " + count);
    }

    /**
     * 埃筛法
     */
    public static int eratosthenes(int num) {
        // false 表示是素数
        boolean[] flag = new boolean[num];

        for (int i = 2; i < num; i++) {
            if (flag[i]) {
                continue;
            }
            if (!isPrime(i)) flag[i] = true;
        }
        int count = 0;
        for (int i = 2; i < flag.length; i++) {
            if (!flag[i]) {
                count++;
            }
        }

        return count;
    }

    /**
     * 暴力算法
     */
    public static int bf(int num) {
        int count = 0;
        for (int i = 2; i < num; i++) {
            if (isPrime(i)) count++;
        }
        return count;
    }

    public static boolean isPrime(int i) {
        // 使用开方，可以减少一半循环
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                return false;
            }
        }
        return true;
    }


}
